#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <cstring>

using namespace std;

class Solution01 {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> vis, hash(wordList.begin(), wordList.end());
        if (!hash.count(endWord)) return 0;
        vis.insert(beginWord);

        int cnt = 0;
        queue<string> q;
        q.push(beginWord);

        int len = beginWord.size();

        while (!q.empty()) {
            cnt++;
            int sz = q.size();
            while (sz--) {
                string t = q.front();
                q.pop();
                // 从这里开始变换
                for (int i = 0; i < len; i++) {
                    string tmp(t);
                    for (char j = 'a'; j <= 'z'; j++) {
                        tmp[i] = j;
                        if (hash.count(tmp) && !vis.count(tmp)) {
                            if (endWord == tmp) return cnt + 1;
                            vis.insert(tmp);
                            q.push(tmp);
                        }
                    }
                }
            }
        }

        return 0;
    }
};

class Solution02 {
    using PII = pair<int, int>;
    int m, n;
    unordered_map<int, PII> hash;
public:

    int cutOffTree(vector<vector<int>>& forest) {
        // 使用hash存储下标，先将数据存储起来
        m = forest.size(), n = forest[0].size();
        vector<int> v;
        
        int first = forest[0][0];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (forest[i][j] > 1) {
                    v.emplace_back(forest[i][j]);
                    hash[forest[i][j]] = make_pair(i, j);
                }
            }
        sort(v.begin(), v.end());
        // 如果first的位置刚好为v的位置，直接开始寻找，假若不是，则需要先从first跑到对应的位置

        int ret = 0;
        if (first != v[0]) {
            int dis = minDistance(forest, v[0], hash[first]);
            if (dis == -1) return -1;
            ret += dis;
        }

        // for (auto e : v) cout << e << " ";

        // for (auto e : v) {
        //     cout << e << "->" << hash[e].first << " " << hash[e].second << endl;
        // }


        int len = v.size();
        for (int i = 0; i < len - 1; i++) {
            int dis = minDistance(forest, v[i + 1], hash[v[i]]);
            if (dis == -1) {
                // cout << i << " " << hash[v[i]].first << hash[v[i]].second << endl;
                // cout << v[i] << " " <<v[i + 1];
                cout << v[i] << " " << hash[v[i]].first << " " << hash[v[i]].second << endl;
                cout << v[i+1] << " " << hash[v[i+1]].first << " " << hash[v[i+1]].second << endl;
                return -1;
            }
            ret += dis;
        }
 
        return ret;
    }



    // vector<vector<bool>> vis;
    bool vis[51][51];

    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int minDistance(vector<vector<int>>& forest, int end, PII startIndex) {
        if (hash[end] == startIndex) return 0;
        // vis.resize(m, vector<bool>().resize(n, false));
        memset(vis, 0, sizeof(vis));
        // 计算最短路径
        queue<PII> q;
        q.push(startIndex);
        vis[startIndex.first][startIndex.second] = true;
        int ret = 0;
        while (!q.empty()) {
            ret++;
            int sz = q.size();
            while (sz--) {
                int a = q.front().first, b = q.front().second;
                // vis[a][b] = true;
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && y >= 0 && x < m && y < n && forest[x][y] && !vis[x][y]) {
                        if (forest[x][y] == end) return ret;
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }

        return -1;
    }
};

class Solution03 {
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int m, n;
    using PII = pair<int, int>;
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        m = mat.size(), n = mat[0].size();
        vector<vector<int>> ret(m, vector<int>(n, -1));
        queue<PII> q;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) 
                if (mat[i][j] == 0) 
                    q.push({i, j}), ret[i][j] = 0;
        while (!q.empty()) {
            int a = q.front().first, b = q.front().second;
            q.pop();
            int num = ret[a][b];
            for (int i = 0; i < 4; i++) {
                int x = a + dx[i], y = b + dy[i];
                if (x >=0 && y >= 0 && x < m && y < n && ret[x][y] == -1) {
                    ret[x][y] = num + 1;
                    q.push({x, y});
                }
            }
        }
        return ret;
    }
};

class Solution04 {
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    using PII = pair<int, int>;
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int onenum = 0, otheronenum = 0;
        for (auto& v : grid) 
            for (auto e : v)
                if (e == 1) onenum++;
            
        vector<vector<int>> vis(m, vector<int>(n, -1));
        queue<PII> q;
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                otheronenum++;
                vis[i][0] = 1;
                q.push({i, 0});
            }
            if (grid[i][n - 1] == 1) {
                otheronenum++;
                vis[i][n - 1] = 1;
                q.push({i, n - 1});                
            }
        }
        
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) {
                otheronenum++;
                vis[0][j] = 1;
                q.push({0, j});
            }
            if (grid[m - 1][j] == 1) {
                otheronenum++;
                vis[m - 1][j] = 1;
                q.push({m - 1, j});                
            }
        }

        while (!q.empty()) {
            int a = q.front().first, b = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && y >= 0 && x < m && y < n && vis[x][y] == -1 && grid[x][y] == 1) {
                    vis[x][y] = 1;
                    otheronenum++;
                    q.push({x, y});
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && vis[i][j] != 1) ret++;
            }
        }
        return ret;
    }
};

class Solution05 {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    using PII = pair<int, int>;

public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> height(m, vector<int>(n, -1));
        queue<PII> q;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j]) {
                    height[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            int a = q.front().first, b = q.front().second;
            q.pop();
            int num = height[a][b];
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && y >= 0 && x < m && y < n && height[x][y] == -1 && isWater[x][y] == 0) {
                    height[x][y] = num + 1;
                    q.push({x, y});
                }
            }            
        }

        return height;
    }
};

class Solution06 {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    using PII = pair<int, int>;

public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<PII> q;
        vector<vector<int>> dist(m, vector<int>(n, -1));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        if (q.empty() || q.size() == m * n)
            return -1;

        int ret = 0;
        while (!q.empty()) {
            int a = q.front().first, b = q.front().second;
            q.pop();
            int num = dist[a][b];
            for (int k = 0; k < 4; k++) {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && y >= 0 && x < m && y < n && dist[x][y] == -1) {
                    dist[x][y] = num + 1;
                    ret = max(ret, num + 1);
                    q.push({x, y});
                }
            }
        }
        return ret;
    }
};

int main() {


    return 0;
}